import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree {
    static class TreeNode{
         public char val;
         public TreeNode left;
         public TreeNode right;
         public TreeNode(char val) {
              this.val = val;
         }
    }
//     public TreeNode createTree() {
//          TreeNode A = new TreeNode('A');
//          TreeNode B = new TreeNode('B');
//          TreeNode C = new TreeNode('C');
//          TreeNode D = new TreeNode('D');
//          TreeNode E = new TreeNode('E');
//          TreeNode F = new TreeNode('F');
//          TreeNode G = new TreeNode('G');
//          TreeNode H = new TreeNode('H');
//
//          A.left = B;
//          A.right = C;
//          B.right = E;
//          B.left = D;
//          C.left = F;
//          C.right = G;
//          E.right = H;
//          return A;
//     }
//     //前序遍历
//     public void preOrder(TreeNode root) {
//         if(root == null) {
//              return ;
//         }
//         System.out.print(root.val + " ");
//         preOrder(root.left);
//         preOrder(root.right);
//     }
//     //中序遍历
//     public void inOrder(TreeNode root) {
//         if(root == null) {
//              return;
//         }
//         inOrder(root.left);
//         System.out.print(root.val + " ");
//         inOrder(root.right);
//     }
//     //后序遍历
//     public void postOrder(TreeNode root) {
//         if(root == null) {
//              return;
//         }
//         postOrder(root.left);
//         postOrder(root.right);
//         System.out.print(root.val + " ");
//     }
//     //层序遍历
//    //求节点个数,遍历法
//    static int nodeNum;
//    public void size1(TreeNode root) {
//        if(root == null) {
//            return;
//        }
//        nodeNum++;
//        size1(root.left);
//        size1(root.right);
//    }
//    //求节点个数,子问题法(节点 = 左树子个数 + 右树子个数 + 1)
//    public int size2(TreeNode root) {
//        if(root == null) {
//            return 0;
//        }
//        return size2(root.left) + size2(root.right) + 1;
//    }
//    /**
//     * 求叶子节点个数,遍历
//     */
//    public int leafSize;
//    public void getLeafNodeCount1(TreeNode root) {
//        //节点不参加判断
//        if(root == null) {
//            return ;
//        }
//        //判断子节点
//        if(root.left == null && root.right == null) {
//            leafSize++;
//        }
//        getLeafNodeCount1(root.left);
//        getLeafNodeCount1(root.right);
//    }
//    /**
//     * 求叶子节点个数,子问题,
//     */
//    public int getLeafNodeCount2(TreeNode root) {
//        if(root == null) {
//            return 0;
//        }
//        if(root.left == null && root.right == null) {
//            return 1;
//        }
//        return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
//    }
//    /**
//     * 求第k层节点个数
//     */
//    public int getKLevelNodeCount(TreeNode root,int k) {
//        //1.判断是否为空
//        //2.判断k是否为1
//        //3.递归使k为1
//        if(root == null) {
//            return 0;
//        }
//        if(k == 1) {
//            return 1;
//        }
//        return getKLevelNodeCount(root.left,k - 1) + getKLevelNodeCount(root.right,k - 1);
//    }
//    /**
//     * 求树的高度
//     */
//    public int getHeight(TreeNode root) {
//        if(root == null) {
//            return 0;
//        }
//        int leftHeight = getHeight(root.left);
//        int rightHeight = getHeight(root.right);
//        return Math.max(leftHeight,rightHeight) + 1;
//    }
//    public int getHeight2(TreeNode root) {
//        //1.判空
//        //2.求左右子树高度
//        if(root == null) {
//            return 0;
//        }
//        int leftHeight = getHeight(root.left);
//        int rightHeight = getHeight(root.right);
//        return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
//    }
//    /**
//     * 检测二叉树中value是否存在
//     */
//    public TreeNode find(TreeNode root,int val) {
//        //1.判断根节点是否存在
//        //2.判断是否相等
//        //3.递归下一个根节点
//        if(root == null) {
//            return null;
//
//        }
//        if(root.val == val) {
//            return root;
//        }
//        TreeNode leftVal = find(root.left,val);
//        if(leftVal != null) {
//            return leftVal;
//        }
//        TreeNode rightVal = find(root.right,val);
//        if(rightVal != null) {
//            return rightVal;
//        }
//        return null;
//    }
        public TreeNode createTree() {
            TreeNode A = new TreeNode('A');
            TreeNode B = new TreeNode('B');
            TreeNode C = new TreeNode('C');
            TreeNode D = new TreeNode('D');
            TreeNode E = new TreeNode('E');
            TreeNode F = new TreeNode('F');
            TreeNode G = new TreeNode('G');
            TreeNode H = new TreeNode('H');
            A.left = B;
            A.right = C;
            B.right = E;
            B.left = D;
            C.left = F;
            C.right = G;
            E.right = H;
            return A;
        }

// 前序遍历
        public void preOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        //1.根
        //2.左
        //3.右
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
        }

        // 中序遍历
        public void inOrder(TreeNode root) {
            if(root == null) {
                return;
            }
            //1.左
            //2.根
            //3.右
            inOrder(root.left);
            System.out.print(root.val + " ");
            inOrder(root.right);
        }

        // 后序遍历
        public void postOrder(TreeNode root) {
            if(root == null) {
                return;
            }
            //1.左
            //2.右
            //3.根
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.val + " ");
        }

        public static int nodeNum;

        /**
         * 获取树中节点的个数：遍历思路
         */
        public void size1(TreeNode root) {
            if(root == null) {
                return;
            }
            nodeNum++;
            size1(root.left);
            size1(root.right);
        }

        /**
         * 获取节点的个数：子问题的思路
         *
         * @param root
         * @return
         */
        public int size2(TreeNode root) {
            if(root == null) {
                return 0;
            }
            //左子树 + 右子树 + 1
            return size2(root.left) + size2(root.right) + 1;
        }


    /*
     获取叶子节点的个数：遍历思路
     */
        public static int leafSize = 0;

        public void getLeafNodeCount1(TreeNode root) {
            if(root == null) {
                return ;
            }
            if(root.left == null && root.right == null) {
                leafSize++;
            }
            getLeafNodeCount1(root.left);
            getLeafNodeCount1(root.right);
        }

    /*
     获取叶子节点的个数：子问题
     */
        public int getLeafNodeCount2(TreeNode root) {
            if(root == null) {
                return 0;
            }
            //左子树 + 右子树 + 1
            if(root.left == null && root.right == null) {
                return 1;
            }
            return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
        }

    /*
    获取第K层节点的个数
     */
        public int getKLevelNodeCount(TreeNode root, int k) {
            if(root == null) {
                return 0;
            }
            if(k == 1) {
                return 1;
            }
            return getKLevelNodeCount(root.left,k - 1) + getKLevelNodeCount(root.right,k - 1);

        }

    /*
     获取二叉树的高度
     时间复杂度：O(N)
     */
        public int getHeight(TreeNode root) {
            if(root == null) {
                return 0;
            }
            int leftHeight = getHeight(root.left);
            int rightHeight = getHeight(root.right);
            return Math.max(leftHeight,rightHeight) + 1;
        }
        // 检测值为value的元素是否存在
        public TreeNode find(TreeNode root, char val) {
            //1.判断根节点
            //2.判断节点值
            //3.下一个值
            if(root == null) {
                return null;
            }
            if(root.val == val) {
                return root;
            }
            TreeNode leftValue = find(root.left,val);
            if(leftValue != null) {
                return leftValue;
            }
            TreeNode rightValue = find(root.right,val);
            if(rightValue != null) {
                return rightValue;
            }
            return null;
        }

        //层序遍历
        public void levelOrder(TreeNode root) {
            //1.判空
            //2.cur循环获取值,并打印
            //3.不为空情况下,把左右节点放入队列中
            if(root == null) {
                return;
            }
            Queue<TreeNode> queue  = new LinkedList<>();
            queue.offer(root);
            //判断是否为空,不为空放入根左右节点
            while(!queue.isEmpty()) {
                TreeNode cur = queue.poll();
                System.out.print(cur.val + " ");
                if(cur.left != null) {
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    queue.offer(cur.right);
                }
            }
        }


        //判断一棵树是不是完全二叉树
        public boolean isCompleteTree(TreeNode root) {
        //1.判空
        if(root == null) {
            return true;
        }
        //2.把头元素放入队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                    break;
                }
            }
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur != null) {
                return false;
            }
        }
        //3.不为空,弹出元素
        //4.判断不为空,并放入左右节点
        //5.为空,判断队列中元素是否全为null
            return true;
        }
}

